package com.atguigu.algorithm.dac;

/**
 * 汉诺塔
 *
 * @author xr-8
 * @date 2023-01-04
 * @time 21:37
 */
public class HanoiTower {

    public static void main(String[] args) {
        hanoiTower(6, 'A', 'B', 'C');
    }

    /**
     * 汉诺塔解法
     *
     * @param num 第几个盘 从上往下数
     * @param a 初始柱
     * @param b 辅助柱
     * @param c 目标柱
     */
    public static void hanoiTower(int num, char a, char b, char c) {
        // 如果只有一个盘
        if (num == 1) {
            System.out.println("第1个盘从" + a + "=>" + c);
        } else { // 如果至少有两个盘，我们可以分成两部分：1、最下面的盘 2、上面的其他盘（即num-1个盘）
            // 1、将上面的其他盘从a 移动到 b, c是辅助柱
            hanoiTower(num - 1, a, c, b);
            // 2、将最下面的盘从a 移动到 b
            System.out.println("第" + num + "个盘从" + a + "=>" + c);
            // 3、将b柱的所有盘（原始上面的其他盘）从b 移动到 c, a是辅助柱
            hanoiTower(num - 1, b, a, c);
        }
    }
}
